package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/double-a-number-represented-as-a-linked-list/description/
 *
 * 2816. 翻倍以链表形式表示的数字
 *
 * 给你一个 非空 链表的头节点 head ，表示一个不含前导零的非负数整数。
 *
 * 将链表 翻倍 后，返回头节点 head 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,8,9]
 * 输出：[3,7,8]
 * 解释：上图中给出的链表，表示数字 189 。返回的链表表示数字 189 * 2 = 378 。
 * 示例 2：
 *
 *
 * 输入：head = [9,9,9]
 * 输出：[1,9,9,8]
 * 解释：上图中给出的链表，表示数字 999 。返回的链表表示数字 999 * 2 = 1998 。
 *
 * @author hanjuntao
 * @date 2025/8/14 0014
 */
public class L_2816_翻倍以链表形式表示的数字 {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(8);
        ListNode node3 = new ListNode(9);
        node1.next = node2;
        node2.next = node3;
        ListNode result = doubleIt3(node1);
        ListNode.print(result);
    }

    /**
     * 思路：
     *
     * 1. 遍历链表，提取数字，放到字符串中
     * 2. 从小到大进行翻倍，将结果存到字符串中
     * 3. 根据翻倍后的结果，重新构造链表
     *
     * 注意点：
     * 不能直接转为整数（int/long） 进行翻倍，会超出范围
     *
     *
     * @param head
     * @return
     */
    public static ListNode doubleIt(ListNode head) {
        if (head == null) {
            return null;
        }

        // 提取数字
        ListNode curr = head;
        StringBuilder sb = new StringBuilder();
        while (curr != null) {
            sb.append(curr.val);
            curr = curr.next;
        }

        String newS = "";

        // 是否进位
        boolean carry = false;

        // 构造翻倍字符串
        for (int i = sb.length() - 1; i >= 0; i--) {
            char c = sb.charAt(i);
            int i1 = Integer.parseInt(String.valueOf(c));
            int result = i1 * 2;
            // 如果上个数有进位，当前数+1
            if (carry) {
                result++;
            }

            // 判断当前数是否需要向前进位
            if (result >= 10) {
                carry = true;
                result = result % 10;
            } else {
                carry = false;
            }

            newS = result + newS;
        }

        // 如果第一个数有进位，则需要构造一个1
        if (carry) {
            newS = "1" + newS;
        }

        // 构造链表
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        for (int j = 0; j < newS.length(); j++) {
            char c = newS.charAt(j);

            cur.next = new ListNode(Integer.parseInt(String.valueOf(c)));
            cur = cur.next;
        }
        return dummy.next;
    }

    /**
     * 思路：
     *
     * 利用反转链表，然后两个链表相加
     *
     *
     *
     * @param head
     * @return
     */
    public static ListNode doubleIt2(ListNode head) {
        return null;
    }

    /**
     * 如果不考虑进位，就是每个节点的值乘以 2。
     *
     * 什么时候会受到进位的影响呢？只有下一个节点大于 4 的时候，才会因为进位多加一。
     *
     * 特别地，如果链表头的值大于 4，那么需要在前面插入一个新的节点。
     *
     * 作者：灵茶山艾府
     * 链接：https://leetcode.cn/problems/double-a-number-represented-as-a-linked-list/solutions/2385962/o1-kong-jian-zuo-fa-kan-cheng-shi-head-y-1dco/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param head
     * @return
     */
    public static ListNode doubleIt3(ListNode head) {
        if (head.val > 4) {
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            head = dummy;
        }

        // 1,4,5,7,3
        for (ListNode cur = head; cur != null; cur = cur.next) {
            cur.val = cur.val * 2 % 10;
            if (cur.next != null && cur.next.val > 4) {
                cur.val++;
            }
        }
        return head;
    }
}
